package com.free.sort;

import java.util.Arrays;

/**
 * 排序工具
 *
 * @author andrew
 *
 */
public final class Sort {
    /**
     * 冒泡排序
     *
     * 基本思想：在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。
     * 即：每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。
     *
     * @param array
     */
    public static <T extends Comparable<? super T>> void bubbleSort(final T[] array) {
        T temp;
        for (int i = array.length - 1; i >= 0; i--) {
            for (int j = 0; j <= i - 1; j++) {
                if (array[j].compareTo(array[j + 1]) > 0) {
                    temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                }
            }
        }
    }

    /**
     * 直接插入排序
     *
     * 基本思想：在要排序的一组数中，假设前面(n-1)[n>=2]个数已经是排好顺序的，现在要把第n个数插到前面的有序数中，
     * 使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
     *
     * @param array
     */
    public static <T extends Comparable<? super T>> void insertSort(final T[] array) {
        T temp = null;
        for (int i = 1; i < array.length; i++) {
            int j = i - 1;
            // 将大于temp的值整体后移一个单位

            for (temp = array[i]; j >= 0 && temp.compareTo(array[j]) < 0; j--) {
                array[j + 1] = array[j];
            }
            // 当移位结束时将temp插入到前半截已经排好序的数组中
            array[j + 1] = temp;
        }
    }

    public static void main(final String[] args) {
        Integer[] array = { 49, 38, 37, 65, 97, 76, 13, 27, 49, 78, 34, 12, 64, 5, 4, 62, 99, 98, 54, 56, 17, 18, 23,
                34, 15, 35, 25, 53, 51 };
        bubbleSort(array);
        System.out.println(Arrays.toString(array));
    }

    /**
     * 简单选择排序
     *
     * 基本思想：在要排序的一组数中，选出最小的一个数与第一个位置的数交换，然后在剩下的数当中再找最小的与第二个位置的数交换，
     * 如此循环到倒数第二个数和最后一个数比较为止。
     *
     * @param array
     */
    public static <T extends Comparable<? super T>> void selectSort(final T[] array) {
        for (int i = 0; i < array.length; i++) {
            T temp = array[i];
            int position = i;
            for (int j = i + 1; j < array.length; j++) {
                if (array[j].compareTo(temp) < 0) {
                    temp = array[j];
                    position = j;
                }
            }
            array[position] = array[i];
            array[i] = temp;
        }
    }

    /**
     * 希尔排序（最小增量排序）
     *
     * 希尔排序属于插入类排序,由Shell提出，希尔排序对直接插入排序进行了简单的改进，基本思想：它通过加大插入排序中元素之间的间隔，
     * 并在这些有间隔的元素中进行插入排序，从而使数据项大跨度地移动，当这些数据项排过一趟序之后，希尔排序算法减小数据项的间隔再进行排序，依次进行下去，
     * 进行这些排序时的数据项之间的间隔被称为增量，习惯上用字母h来表示这个增量。
     *
     * 常用的h序列由Knuth提出，该序列从1开始，通过如下公式产生：
     *
     * h = 3 * h +1
     *
     * 反过来程序需要反向计算h序列，应该使用
     *
     * h=(h-1)/3
     *
     * @param array
     */
    public static <T extends Comparable<? super T>> void shellSort(final T[] array) {
        // 计算出最大的h值
        int h = 1;
        while ((h * 3 + 1) < array.length) {
            h = 3 * h + 1;
        }
        while (h > 0) {
            for (int i = h - 1; i < array.length; i++) {
                T temp = array[i];
                int j = i;
                for (; (j >= h) && (array[j - h].compareTo(temp) > 0); j -= h) {
                    array[j] = array[j - h];
                }
                array[j] = temp;
            }
            h /= 3;
        }
    }

    private Sort() {
    }
}
